package com.mango.leet.code.week2.game375;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

/**
 * 100155. 双模幂运算
 * ((aibi % 10)ci) % mi == target
 * https://leetcode.cn/contest/weekly-contest-375/problems/double-modular-exponentiation/
 */
public class LC100155 {
    // variables[0] = [2,3,3,10] ，(23 % 10)3 % 10 = 2
    public static List<Integer> getGoodIndices(int[][] variables, int target) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < variables.length; i++) {
            BigInteger a = new BigInteger(variables[i][0]+"");
            BigInteger b = new BigInteger(variables[i][1]+"");
            BigInteger c = new BigInteger(variables[i][2]+"");
            BigInteger m = new BigInteger(variables[i][3]+"");
            if (m.intValue() == 0) {
                continue;
            }
            BigInteger x = a.pow(b.intValue());
            BigInteger mod = x.mod(BigInteger.valueOf(10));
            BigInteger y = mod.pow(c.intValue());
            if (y.mod(m).intValue() == target) {
                res.add(i);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[][] variables = {
                {2,3,3,10},
                {0,0,0,0},
                {6,1,1,4}
        };
        int target = 2;
        int[][] variables1 = {
                {1000,1000,1000,1000}
        };
        int target1 = 17;
        System.out.println(getGoodIndices(variables,target));
        System.out.println(getGoodIndices(variables1,target1));
    }
}
